package com.test.daily.leetcode.y2022.m06.day0610.v04;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/10 下午 08:59
 * @version: 1.0
 */
public class Solution {
    public int countPalindromicSubsequences(String s) {
        int mod = 10^9 + 7;
        int N = s.length();
        int[][] dp = new int[N][N];
        for(int i = 0; i < N; i++){
            dp[i][i] = 1;
        }
        for(int len = 2; len <= N; len++){
            for(int i = 0; i + len <=N; i++){
                int j = i + len - 1;
                if(s.charAt(i) == s.charAt(j)){
                    int left = i +1;
                    int right = j - 1;
                    while(left <= right && s.charAt(i) != s.charAt(left)){
                        left++;
                    }
                    while(left <= right && s.charAt(right) != s.charAt(j)){
                        right--;
                    }
                    // no dupliicate
                    if(left > right){
                        dp[i][j] = 2 * dp[i+1][j-1] + 2;
                        // duplicate 1
                    } else if(left == right){
                        dp[i][j] = 2 * dp[i+1][j-1] + 1;
                        // duplicate 2 and above
                    } else {
                        dp[i][j] = 2 * dp[i+1][j-1] - dp[left+1][right - 1];
                    }

                } else {
                    dp[i][j] = dp[i][j-1] + dp[i+ 1][j] - dp[i+1][j-1];
                }
                dp[i][j] = dp[i][j] % mod >= 0? dp[i][j] %mod: dp[i][j] + mod;
            }
        }
        return dp[0][N-1];
    }
}
